The present invention relates to techniques for mapping functions to lookup tables on programmable circuits, and more particularly, to techniques for mapping functions to lookup tables that reduce the amount of circuitry needed to implement the functions.
A field programmable gate array (FPGA) is a programmable integrated circuit. Programmable integrated circuits also include programmable logic devices (PLDs), programmable logic arrays (PLAs), configurable logic arrays, etc. Many programmable integrated circuits are hybrids of FPGAs and ASICs (application specific integrated circuits).
FPGAs typically include programmable logic blocks, programmable routing resources, and programmable input/output (I/O) blocks. Each programmable logic block typically contain combinatorial components such as multiplexers and lookup tables as well as sequential components such as flip-flops.
Lookup tables are the basic logic blocks in many FPGAs today. A lookup table (LUT) includes memory cells that can store the truth tables of an arbitrary function. A LUT with k inputs can implement a function with k input variables. A LUT stores an output value corresponding to each set of input values. The pattern of output values describes the function.
A LUT receives a set of N digital input signals. The input signals are treated as a binary value with N bits. The binary value of the input signals are used as a memory address to access one of the LUT memory locations. A LUT outputs bits stored in the memory location. The memory location has an address corresponding to the binary value of the input signals.
A programmable integrated circuit is configured to implement a design provided by a user. Typically, the types of circuit elements in a user design do not correspond to the types of circuit elements in the FPGA, because users are not usually aware of the particular architecture of the FPGA. For example, the user typically does not implement the user design using LUTs.
Lookup tables and other circuit elements in the FPGA are selected to implement equivalent functions in the user design. This selection process involves synthesis and technology mapping. During synthesis, the user-made design is converted into a network of logic gates. During technology mapping, the logic gates are converted into logic blocks on the FPGA. Logic blocks are blocks on the FPGA that contain LUTs and registers.
Shannon expansion is a well known technique that maps a Boolean function to a set of lookup tables. However, as the number of input variables to the function increases, Shannon expansion maps the function to a disproportionately larger number of logic blocks.
For example, if each logic block on an FPGA has one 6-input LUT, Shannon expansion can be used to map a 7-input variable function to 3 logic blocks, a 10-input variable function to 21 logic blocks, and a 12-input variable function to 85 logic blocks.
Therefore, it would be desirable to reduce the number of lookup tables that are needed to implement functions on a programmable integrated circuit.